/*
 * Copyright (C), 2015-2018
 * FileName: Solution107
 * Author:   zhao
 * Date:     2018/9/9 14:22
 * Description: 107. 二叉树的层次遍历 II
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredtwo;

import com.lizhaoblog.diynode.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * 〈一句话功能简述〉<br>
 * 〈107. 二叉树的层次遍历 II〉
 *
 * @author zhao
 * @date 2018/9/9 14:22
 * @since 1.0.1
 */
public class Solution107 {
  /**************************************
   * 题目
   给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

   例如：
   给定二叉树 [3,9,20,null,null,15,7],

   3
   / \
   9  20
   /  \
   15   7
   返回其自底向上的层次遍历为：

   [
   [15,7],
   [9,20],
   [3]
   ]
   **************************************/

  /**************************************
   *
   * 想法：
   *    根据104题的递归方法
   *    将所有的数据存到一个数组中
   *    最后进行翻转
   * 我的做法
   *    超过91.17的测试案例
   * 总结：
   *
   * ***********************************/
  public List<List<Integer>> levelOrderBottom(TreeNode root) {
    ArrayList<List<Integer>> lists = new ArrayList<>();
    recPushToArr(root, 0, lists);
    Collections.reverse(lists);
    return lists;
  }

  private void recPushToArr(TreeNode root, int depth, List<List<Integer>> lists) {
    if (root == null) {
      return;
    }
    List<Integer> integers = null;
    if (depth >= lists.size()) {
      integers = new ArrayList<>();
      lists.add(integers);
    } else {
      integers = lists.get(depth);
    }
    integers.add(root.val);

    if (root.left == null && root.right == null) {
      return;
    }
    depth++;
    recPushToArr(root.left, depth, lists);
    recPushToArr(root.right, depth, lists);
  }

  /**************************************
   * 比我好的答案
   * ***********************************/
  public List<List<Integer>> better(TreeNode root) {
    LinkedList<List<Integer>> l = new LinkedList();
    if (root == null) {
      return l;
    }
    Queue<TreeNode> q = new LinkedList();
    Stack<List<Integer>> s = new Stack();
    q.offer(root);
    int i = q.size();
    List<Integer> list = new LinkedList();
    TreeNode p = null;
    while (q.size() > 0) {
      if (i == 0) {
        l.addFirst(list);
        i = q.size();
        list = new LinkedList();
      }

      p = q.poll();
      list.add(p.val);

      --i;

      if (p.left != null) {
        q.offer(p.left);
      }
      if (p.right != null) {
        q.offer(p.right);
      }

    }

    l.addFirst(list);

    return l;
  }
}
